Funciones y expresiones booleanas

El paquete sympy tiene un módulo de lógica. Con él podemos hacer algunas simplificaciones



In [1]:

    
from sympy import *

Definimos los símbolos que vamos a utilizar. Supremo e ínfimo se introducen usando el o e y lógicos. Aunque también podemos utilizar And y Or como funciones. Para la negación usamos Not o ~. Tenemos además Xor, Nand, Implies (que se puede usar de forma prefija con >>) y Equivalent.



In [2]:

    
x, y, z = symbols("x,y,z")



In [3]:

    
p = (x | y) & ~ z



In [4]:

    
pprint(p)









    



¬z ∧ (x ∨ y)

La formas normales conjuntiva y disyuntivas las podemos calcular como sigue



In [5]:

    
to_cnf(p)









    Out[5]:





And(Not(z), Or(x, y))



In [6]:

    
to_dnf(p)









    Out[6]:





Or(And(Not(z), x), And(Not(z), y))

También podemos simplificar expresiones



In [7]:

    
simplify(x | ~x)









    Out[7]:





True

O dar valores de verdad a las variables



In [8]:

    
p.xreplace({x:True})









    Out[8]:





Not(z)

Esto nos permite crear nuestras propias tablas de verdad



In [9]:

    
p.free_symbols









    Out[9]:





{x, y, z}



In [10]:

    
p = Or(x,And(x,y))



In [11]:

    
from IPython.display import HTML,display



In [12]:

    
colores=['LightCoral','Aquamarine']
tabla="<table style='width:25%'><tr><td bgcolor='lightblue'>$"+latex(x)
tabla=tabla+"$ </td><td bgcolor='lightblue'>$"+latex( y)+"$</td><td bgcolor='lightblue'>$"+latex(p)+"$</td></tr>"
for t in cartes({True,False}, repeat=2):
    v =dict(zip((x,y),t))
    tabla=tabla+"<tr> <td bgcolor="+colores[v[x]]+">"+str(v[x])
    tabla=tabla+"</td><td bgcolor="+colores[v[y]]+">"+str(v[y])
    tabla=tabla+"</td><td bgcolor="+colores[v[x]]+">"+str(p.xreplace(v))+"</td></tr>"
tabla=tabla+"</table>"
display(HTML(tabla))









    




$x$ $y$ $x \vee \left(x \wedge y\right)$
 False False False
 False True False
 True False True
 True True True

Una forma de comprobar que dos expresiones son equivalentes es la siguiente



In [13]:

    
Equivalent(simplify(p), simplify(x))









    Out[13]:





True

Veamos ahora cómo podemos encontrar la versión simplificada de una función booleana que venga dada por minterms. Aparentemente SOPform hace algunas simplificaciones usando el algoritmo de Quine-McCluskey



In [14]:

    
p=SOPform([x,y,z],[[0,0,1],[0,1,0],[0,1,1],[1,1,0],[1,0,0],[1,0,1]])



In [15]:

    
p









    Out[15]:





Or(And(Not(x), y), And(Not(x), z), And(Not(y), z), And(Not(z), x), And(Not(z), y))

Al utilizar sympy podemos escribir una forma más amigable de una expresión booleana



In [16]:

    
pprint(p)









    



(x ∧ ¬z) ∨ (y ∧ ¬x) ∨ (y ∧ ¬z) ∨ (z ∧ ¬x) ∨ (z ∧ ¬y)

Los comandos simplify or simplify_logic pueden simplificar aún más



In [17]:

    
pprint(simplify(p))









    



(x ∧ ¬y) ∨ (x ∧ ¬z) ∨ (y ∧ ¬x) ∨ (z ∧ ¬y)



In [18]:

    
pprint(simplify_logic(p))









    



(x ∧ ¬y) ∨ (x ∧ ¬z) ∨ (y ∧ ¬x) ∨ (z ∧ ¬y)

De hecho, p se puede escribir de forma más compacta. Para ello vamos a utilizar el algoritmo espresso, que viene implementado en el paquete pyeda



In [19]:

    
from pyeda.inter import *

Este paquete no admite las variables definidas con symbols, así que las vamos a declarar con expvar para definir variables booleanas



In [20]:

    
x,y,z = map(exprvar,"xyz")



In [21]:

    
p=SOPform([x,y,z],[[0,0,1],[0,1,0],[0,1,1],[1,1,0],[1,0,0],[1,0,1]])

Otro problema es que la salida de SOPform no es una expresión de pyeda. Lo podemos arreglar pasándola a cadena de caracteres y releyéndola en pyeda



In [22]:

    
p=expr(str(p))

Ahora sí que podemos utilizar el simplificador espresso implementado en pyeda



In [23]:

    
pm, =espresso_exprs(p)



In [24]:

    
pm









    Out[24]:





Or(And(x, ~z), And(~x, y), And(~y, z))

Y podemos comprobar que es más corta que la salida que daba sympy. Para escribirla de forma más "legible" volvemos a utilizar pprint de sympy, pero para ello necesitamos pasar nuestra expresión en pyeda a sympy



In [25]:

    
pprint(sympify(pm))









    



(x ∧ ¬z) ∨ (y ∧ ¬x) ∨ (z ∧ ¬y)

Podríamos haber definido directamente p utilizando tablas de verdad



In [26]:

    
p=truthtable([x,y,z], "01111110")



In [27]:

    
pm, = espresso_tts(p)



In [28]:

    
pprint(sympify(pm))









    



(x ∧ ¬z) ∨ (y ∧ ¬x) ∨ (z ∧ ¬y)

La tabla de verdad de una expresión se obtiene como sigue



In [29]:

    
expr2truthtable(pm)

Veamos un ejemplo análogo pero con más variables, y de paso mostramos como definir vectores de variables



In [30]:

    
X = ttvars('x', 4)
f = truthtable(X, "0111111111111110")



In [31]:

    
fm, = espresso_tts(f)



In [32]:

    
fm









    Out[32]:





Or(And(~x[0], x[1]), And(~x[1], x[2]), And(x[0], ~x[3]), And(~x[2], x[3]))



In [33]:

    
expr2truthtable(fm)









    Out[33]:





x[3] x[2] x[1] x[0]
   0    0    0    0 : 0
   0    0    0    1 : 1
   0    0    1    0 : 1
   0    0    1    1 : 1
   0    1    0    0 : 1
   0    1    0    1 : 1
   0    1    1    0 : 1
   0    1    1    1 : 1
   1    0    0    0 : 1
   1    0    0    1 : 1
   1    0    1    0 : 1
   1    0    1    1 : 1
   1    1    0    0 : 1
   1    1    0    1 : 1
   1    1    1    0 : 1
   1    1    1    1 : 0

Un ejemplo de simplificación

Veamos que el o exclusivo con la definición $x\oplus y=(x\wedge \neg y)\vee (\neg x\wedge y)$ es asociativo



In [34]:

    
x, y, z = map(exprvar,"xyz")



In [35]:

    
f = lambda x,y : Or(And(x,~ y),And(~x,y))



In [36]:

    
f(x,y)









    Out[36]:





Or(And(x, ~y), And(~x, y))



In [37]:

    
expr2truthtable(f(x,y))









    Out[37]:





y x
0 0 : 0
0 1 : 1
1 0 : 1
1 1 : 0



In [38]:

    
f(x,y).equivalent(Xor(x,y))









    Out[38]:





True

Veamos que efectivamente $x\oplus(y\oplus z)=(x\oplus y)\oplus z$



In [39]:

    
pprint(simplify_logic(f(x,f(y,z))))









    



(x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (y ∧ ¬x ∧ ¬z) ∨ (z ∧ ¬x ∧ ¬y)



In [40]:

    
pprint(simplify_logic(f(f(x,y),z)))









    



(x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (y ∧ ¬x ∧ ¬z) ∨ (z ∧ ¬x ∧ ¬y)



In [41]:

    
a= f(f(x,y),z)
b= f(x,f(y,z))



In [42]:

    
a.equivalent(b)









    Out[42]:





True

Podemos hacer una función que pase de minterm a expresions en pyeda



In [43]:

    
def minterm2expr(l,v):
    n = len(l)
    vv=v.copy()
    for i in range(n):
        if not(l[i]):
            vv[i]=Not(vv[i])
    return And(*vv)



In [44]:

    
x,y,z,t = map(exprvar,"xyzt")



In [45]:

    
minterm2expr([0,1,0,1],[x,y,z,t])









    Out[45]:





And(~x, y, ~z, t)



In [46]:

    
def minterms2expr(l,v):
    return Or(*[minterm2expr(a,v) for a in l])



In [47]:

    
hh2=minterms2expr([[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,1,1,0],[0,1,1,1],[1,0,0,0],[1,0,1,0],[1,1,0,0]],[x,y,z,t])



In [48]:

    
hh2









    Out[48]:





Or(And(x, y, ~z, ~t), And(~x, ~y, z, ~t), And(~x, y, ~z, ~t), And(~x, y, z, ~t), And(~x, y, z, t), And(x, ~y, ~z, ~t), And(x, ~y, z, ~t), And(~x, ~y, ~z, ~t))



In [49]:

    
pprint(sympify(hh2))









    



(t ∧ y ∧ z ∧ ¬x) ∨ (x ∧ y ∧ ¬t ∧ ¬z) ∨ (x ∧ z ∧ ¬t ∧ ¬y) ∨ (x ∧ ¬t ∧ ¬y ∧ ¬z) 
∨ (y ∧ z ∧ ¬t ∧ ¬x) ∨ (y ∧ ¬t ∧ ¬x ∧ ¬z) ∨ (z ∧ ¬t ∧ ¬x ∧ ¬y) ∨ (¬t ∧ ¬x ∧ ¬y 
∧ ¬z)

Y ahora la podemos simplificar



In [50]:

    
sh2, = espresso_exprs(hh2)



In [51]:

    
sh2









    Out[51]:





Or(And(~z, ~t), And(~y, ~t), And(~x, y, z))

$x$	$y$	$x \vee \left(x \wedge y\right)$
False	False	False
False	True	False
True	False	True
True	True	True